import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * 最小k个数
 */
public class Solution40 {

    /**
     * 大根堆
     * @param nums
     * @param k
     * @return
     */
    public ArrayList<Integer> getKthSmallestNumbers1(int[] nums, int k){

        if (k > nums.length || k <= 0)
            return new ArrayList<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);//Java默认是小根堆，所以需要重写比较器
        for (int num : nums){
            maxHeap.offer(num);
            if (maxHeap.size() > k)
                maxHeap.poll();
        }
        return new ArrayList<>(maxHeap);
    }

    /**
     * 快速选择算法（快速排序思想）
     * @param nums
     * @param k
     * @return
     */
    public ArrayList<Integer> getKthSmallestNumbers2(int[] nums, int k){
        ArrayList<Integer> ret = new ArrayList<>();
        if (k > nums.length || k <= 0)
            return ret;
        findKthSmallest(nums, k);
        for (int i = 0; i < k; i++)
            ret.add(nums[i]);
        return ret;
    }

    public void findKthSmallest(int[] nums, int k){
        int l = 0, h = nums.length;
        while (l < h){
            int j = partition(nums, l, h);
            if (j == k)
                break;
            if (j > k)
                h = j - 1;
            else
                l = j + 1;
        }
    }

    private int partition(int[] nums, int l, int h){
        int p = nums[l];
        int i = l, j = h + 1;
        while (true){
            while (i != h && nums[++i] < p);
            while (j != l && nums[--j] > p);
            if (i >= j)
                break;
            swap(nums, i, j);
        }
        swap(nums, l, j);
        return j;
    }

    private void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
